package com.platform.modules.alg.hdu2874;

public class Hdu2874 {
    private final int maxn = 10000;
    private final int maxq = 1000000;
    Node e[] = new Node[2 * maxn];
    Query qe[] = new Query[2 * maxq];

    int ehead[] = new int[maxn];
    int dis[] = new int[maxn];
    int fa[] = new int[maxn];
    int ecnt;
    int vis[] = new int[maxn];

    int qhead[] = new int[maxn];
    int ans[] = new int[maxq];
    int qcnt;
    int n, m, c;

    void init() {
        ecnt = qcnt = 0;
        ehead = new int[maxn];
        for (int i = 0; i < ehead.length; i++) {
            ehead[i] = -1;
        }
        qhead = new int[maxn];
        for (int i = 0; i < qhead.length; i++) {
            qhead[i] = -1;
        }

        vis = new int[maxn];
        for (int i = 0; i < vis.length; i++) {
            vis[i] = -1;
        }

        for (int i = 0; i < e.length; i++) {
            e[i] = new Node();
        }

        for (int i = 0; i < qe.length; i++) {
            qe[i] = new Query();
        }
    }

    void add1(int u, int v, int w) {
        e[ecnt].to = v;
        e[ecnt].w = w;
        e[ecnt].next = ehead[u];
        ehead[u] = ecnt++;
    }

    void add2(int u, int v, int id) {
        qe[qcnt].id = id;
        qe[qcnt].to = v;
        qe[qcnt].next = qhead[u];
        qhead[u] = qcnt++;
    }


    int Find(int x) {
        if (x != fa[x])
            fa[x] = Find(fa[x]);
        return fa[x];
    }

    void LCA(int u, int deep, int root) {
        fa[u] = u;
        dis[u] = deep;
        vis[u] = root;
        for (int i = ehead[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (vis[v] == -1) {
                LCA(v, deep + e[i].w, root);
                fa[v] = u;
            }
        }
        for (int i = qhead[u]; i != -1; i = qe[i].next) {
            int v = qe[i].to;
            if (vis[v] == root)
                ans[qe[i].id] = dis[v] + dis[u] - 2 * dis[Find(v)];
        }
    }

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[1]);
        c = Integer.parseInt(word[2]);

        int u, v, w;
        init();

        for (int i = 1; i <= m; i++) {
            String[] info = line[i].split(" ");
            u = Integer.parseInt(info[0]);
            v = Integer.parseInt(info[1]);
            w = Integer.parseInt(info[2]);
            add1(u, v, w);
            add1(v, u, w);
        }

        for (int i = 0; i < c; i++) {
            String[] query = line[i + m + 1].split(" ");
            u = Integer.parseInt(query[0]);
            v = Integer.parseInt(query[1]);
            ans[i] = -1;
            add2(u, v, i);
            add2(v, u, i);
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == -1)
                LCA(i, 0, i);
        }
        for (int i = 0; i < c; i++) {
            if (ans[i] == -1) output += "Not connected\n";
            else output += ans[i] + "\n";
        }


        return output;
    }
}

// 边
class Node {
    public int to; // 邻接点
    public int w; // 边权
    public int next; // 下一条边的下标
}

class Query {
    public int to;
    public int id; // 查询的编号
    public int next;
}
